package hotLeetcode;

import java.security.Key;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class H560Leetcode {
    public int subarraySum1(int[] nums, int k) {
        int  res = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];

                if (sum == k) {
                    res++;
                }


            }

        }

        return res;
    }
    int[] s;
    //前缀和解法
    public int subarraySum2(int[] nums, int k) {
        //  1 2 3 4  5  6 求前缀和  k = 6
        //0,1,3,6,10,15,21
        int count = 0;
        Map<Integer, Integer> hashMap = new HashMap<>();
        s = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            s[i + 1] = nums[i] + s[i];
            hashMap.put(i + 1, s[i + 1]);
        }
        //用hash 记录次数


        for (int i = 0; i < s.length; i++) {
            int key = s[i] - k;
            if (hashMap.containsKey(key)) {
                count++;
            }
        }



        return count;

    }

    public int subarraySum(int[] nums, int k) {
        //  1 2 3 4  5  6 求前缀和  k = 6
        //0,1,3,6,10,15,21
        int count = 0;
        int pre = 0;

        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,1);
        for (int i = 0; i < nums.length; i++) {
            pre += nums[i];

            if (map.containsKey(pre - k)) {
                count += map.get(pre - k);
            }

            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }

        return count;



    }

    public static void main(String[] args) {
        int[] nums = {1,1,1};
        int k = 2;
        H560Leetcode h560Leetcode = new H560Leetcode();
        System.out.println(h560Leetcode.subarraySum(nums, k));
    }
}
